package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/13 9:46
 */
public class C363 {

    // https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/
    // 暴力解, 先把每一行转成前缀和, 然后暴力尝试往下往右走
    public static int maxSumSubmatrix(int[][] matrix, int k) {
        int R = matrix.length;
        int C = matrix[0].length;
        for (int r = 0; r < R; r++) {
            for (int c = 1; c < C; c++) {
                matrix[r][c] += matrix[r][c - 1];
            }
        }
        return process(matrix, k, R, C, 0, 0, 0, 0);
    }

    private static int process(int[][] matrix, int k, int R, int C, int r1, int c1, int r2, int c2) {
        if (r1 == R || c1 == C || r2 == R || c2 == C || r1 > r2 || c1 > c2) {
            return Integer.MIN_VALUE;
        }
        // 计算下累加和
        int sum = 0;
        for (int i = r1; i <= r2; i++) {
            sum += (matrix[i][c2] - (c1 - 1 < 0 ? 0 : matrix[i][c1 - 1]));  // 累加和数组. [c1 ~ c2]的累加和 = [0~c2] - [0~c1-1]
        }
        if (sum > k) {
            sum = Integer.MIN_VALUE;
        }
        int p1 = process(matrix, k, R, C, r1 + 1, c1, r2, c2);
        int p2 = process(matrix, k, R, C, r1, c1 + 1, r2, c2);
        int p3 = process(matrix, k, R, C, r1, c1, r2 + 1, c2);
        int p4 = process(matrix, k, R, C, r1, c1, r2, c2 + 1);
        int ans = Math.max(p1, Math.max(p2, Math.max(p3, Math.max(p4, sum))));
        return ans;
    }

    // 行数远大于列数
    // 先正常转dp
    public static int dp(int[][] matrix, int k) {
        int R = matrix.length;
        int C = matrix[0].length;
        for (int r = 0; r < R; r++) {
            for (int c = 1; c < C; c++) {
                matrix[r][c] += matrix[r][c - 1];
            }
        }
        int[][][][] dp = new int[R + 1][R + 1][C + 1][C + 1];
        for (int r1 = R; r1 >= 0; r1--) {
            for (int r2 = R; r2 >= r1; r2--) {
                for (int c1 = C; c1 >= 0; c1--) {
                    for (int c2 = C; c2 >= c1; c2--) {
                        if (r1 == R || r2 == R || c1 == C || c2 == C /*|| r1 > r2 || c1 > c2*/) {
                            dp[r1][r2][c1][c2] = Integer.MIN_VALUE;
                            continue;
                        }
                        int sum = 0;
                        for (int i = r1; i <= r2; i++) {
                            sum += (matrix[i][c2] - (c1 - 1 < 0 ? 0 : matrix[i][c1 - 1]));  // 累加和数组. [c1 ~ c2]的累加和 = [0~c2] - [0~c1-1]
                        }
                        System.out.println("r1: " + r1 + ", r2: " + r2 + ", c1: " + c1 + ", c2: " + c2 + ",sum: " + sum);
                        if (sum > k) {
                            sum = Integer.MIN_VALUE;
                        }
                        int p1 = dp[r1 + 1][r2][c1][c2];
                        int p2 = dp[r1][r2 + 1][c1][c2];
                        int p3 = dp[r1][r2][c1 + 1][c2];
                        int p4 = dp[r1][r2][c1][c2 + 1];
                        int ans = Math.max(p1, Math.max(p2, Math.max(p3, Math.max(p4, sum))));
                        dp[r1][r2][c1][c2] = ans;
                    }
                }
            }
        }

        return dp[0][0][0][0];
    }


    // for test
    public static void main(String[] args) {
//        int[][] matrix = {{1, 0, 1}, {0, -2, 3}};
//        int[][] matrix = {{2, 2, -1}};
//        int[][] matrix2 = {{2, 2, -1}};
//        int k = 0;
        int[][] matrix = {
                {7, 7, 4, -6, -10},
                {9, 6, -3, -7, 7},
                {-4, 1, 4, -3, -8},
                {-7, -4, -4, 6, -10},
                {1, 3, -2, 3, -10},
                {8, -2, 1, 1, -8},
        };
        int[][] matrix2 = {
                {7, 7, 4, -6, -10},
                {9, 6, -3, -7, 7},
                {-4, 1, 4, -3, -8},
                {-7, -4, -4, 6, -10},
                {1, 3, -2, 3, -10},
                {8, -2, 1, 1, -8},
        };
        int k = 12;
        System.out.println(maxSumSubmatrix(matrix, k));
        System.out.println(dp(matrix2, k));
    }

}
